#include "suffixindex.h"

void SuffixSorter::Init(Corpus * corpus, IntegerArray *positions) {
  corpus_ = corpus;
  positions_ = positions;
  cout << "positions_->size():" << positions_->size() << endl;
}

void SuffixSorter::Sort() {
  cout << "start indexing" << endl;
  int64 before = TimeNS();
  MakeRollingHash();
  PositionCompare comp(this);
  cout << "Finished building rolling hash" << endl;

  JQSort<IntegerArray::iterator, uint64, PositionCompare>
    (positions_->begin(), positions_->end(), &comp, G_JQ);

  /*
  uint64 * sorting = new uint64[positions_->size()];
  for (uint64 i=0; i<positions_->size(); i++)
    sorting[i] = positions_->Get(i);
  JQSort<uint64*, uint64, PositionCompare>
    (sorting, sorting + positions_->size(), &comp, G_JQ);
   //sort(sorting, sorting + positions_->size(), comp);
  for (uint64 i=0; i<positions_->size(); i++)
    positions_->Set(i, sorting[i]);
  */

  int64 after = TimeNS();
  // GTrackReferences = true;
  VerifySort();
  // GTrackReferences = false;
  cout << "time to index in ns:" << Delimit(after- before) << endl;
}

// Store things so they can be read back into an IntegerArray
void SuffixSorter::Store(string fn) {
  ofstream output(fn.c_str(), ofstream::binary);
  // uint64 integer_size = CeilingLg2(corpus_->size());
  positions_->Write(&output);
  //IntegerArray::ConvertAndStream(&output, positions_, 
  // positions_size_, integer_size);
}

void SuffixSorter::VerifySort() {
  cout << "::VerifySort\n";
  cout << "positions_.size():" << positions_->size() << endl;
  cout << "positions_:" << positions_ << endl;
  for (uint64 i=0; i+1 < positions_->size(); i++) {
    uint64 p0 = (*positions_)[i];
    uint64 p1 = (*positions_)[i+1];
    CHECK(CompareSuffixes(p0, p1) < 0);
    CHECK(CompareSuffixes(p1, p0) > 0);
  }
}

/*
  This index allows a rolling hash over any subsequence to be computed in O(1)
  We store some elements of a virtual array a defined by 
  a[-1] = 0
  a[i] = k * a[i-1] + s[i] (mod n)
  
  the hash of a substring 
  = s[begin .. end) = a[end-1] - a[begin-1] * k^(end-begin)
*/
void SuffixSorter::MakeRollingHash() {
  k_ = 9084723423141ll;
  k_pow_2_pow_n_ = new uint64[100];
  k_pow_2_pow_n_[0] = k_;
  for (int i=1; i<100; i++) 
    k_pow_2_pow_n_[i] = k_pow_2_pow_n_[i-1] * k_pow_2_pow_n_[i-1];
  rolling_hash_sparsity_ = 16;
  rolling_hash_ = new uint64[1 + (corpus_->size() / rolling_hash_sparsity_)];
  uint64 last_val = 0;
  for (uint64 i=0; i<corpus_->size(); i++) {
    if (i % 100000000 == 0) cout << "Building rolling hash " << i << endl;
    last_val = last_val * k_ + (*corpus_)[i];
    if (i % rolling_hash_sparsity_ == 0)
      rolling_hash_[i / rolling_hash_sparsity_] = last_val;
  }
}

/* 
   returns a[n-1], as defined above. 
   The hash of a substring s[begin .. end) 
   = PointRollingHash(end) - k^end-begin * PointRollingHash(begin)
*/
uint64 SuffixSorter::PointRollingHash(uint64 n) {
  if (n==0) return 0;
    n--;
    uint64 ret = rolling_hash_[n / rolling_hash_sparsity_];
    for (uint64 i = (n / rolling_hash_sparsity_) * rolling_hash_sparsity_ + 1; 
	 i<=n; i++) {
      ret = ret * k_ + (*corpus_)[i]; }
    return ret; }

// Only for debugging
uint64 SuffixSorter::ComputeRollingHash(uint64 begin, uint64 end){
  //hash_counter++;
  return PointRollingHash(end) - PointRollingHash(begin) 
    * UInt64Pow(k_, end - begin); }

// lexicographic compare of suffixes starting from positions p1 and p2
// strcmp style return value
// mega-compilcated to avoid quadratic complexity on lots of repetitions
int64 SuffixSorter::CompareSuffixes(uint64 p1, uint64 p2) {
  if (p1 == p2) return 0;
  //comparison_counter++;
  uint64 l1 = corpus_->size() - p1;
  uint64 l2 = corpus_->size() - p2;
  uint64 shorter = min(l1, l2);
  int log_step = 7;
  uint64 step = (1 << log_step);
  // Do some amount of naive comparison to see if we have an early difference.
  for (uint64 i=0; i<step; i++) {
    if (i == shorter) return (l1 < l2) ? -1 : 1;
    uint32 t1 = (*corpus_)[p1+i];
    uint32 t2 = (*corpus_)[p2+i];
    if (t1 < t2) return -1;
    if (t2 < t1) return 1;
  }    

  // Here we find the largest value n such that the first n values starting at
  // p1 are equal to the first n values starting at p2.  
  uint64 point_hash_1 = PointRollingHash(p1);
  uint64 point_hash_2 = PointRollingHash(p2);
  uint64 point_hash_difference = point_hash_1 - point_hash_2;
  // we know that low <= n < high 
  uint64 low = step;
  uint64 k_pow_low = k_pow_2_pow_n_[log_step];
  uint64 high = shorter + 1;
  while (low + 1 != high) {
    // our step should be at least 1, but less than high-low
    log_step++;
    step *= 2;
    while (low + step >= high) {
	log_step--;
	step /= 2;
    }
    uint64 mid = low + step;
    uint64 k_pow_mid = k_pow_low * k_pow_2_pow_n_[log_step];
    bool match = ( (PointRollingHash(p1 + mid) - PointRollingHash(p2 + mid)
		    - point_hash_difference * k_pow_mid) == 0);
    if (match) {
      low = mid;
      k_pow_low = k_pow_mid;
    } else {
      high = mid;
    }
  }
    // identical_character_counter += low;
  if (low == shorter) return (l1 < l2) ? -1 : 1;
  // for (uint64 i=0; i<low; i++) CHECK((*corpus_)[p1+i] == (*corpus_)[p2+i]);
  // CHECK((*corpus_)[p1+low] != (*corpus_)[p2+low]);
  return ((*corpus_)[p1+low] < (*corpus_)[p2+low]) ? -1 : 1;
}

void SuffixIndex::Init(Corpus * corpus, Memblock index) {
  corpus_ = corpus;
  index_.Load(index);
  // VerifySort();
}

// Input string is byte range with begin/length
// Output is a start and length in the sorted suffix array
pair<uint64, int64>
SuffixIndex::Search(uint32 *target_begin, uint64 target_length) {
  /* cout << "Search "
     << " target_length = " << target_length
     << " index_.size() = " << index_.size() << endl; */
  Searcher s(this, target_begin, target_length, false); 
  uint64 match_begin = FirstSatisfaction(0, index_.size(), s);
  s.second_wins_ = true;
  uint64 match_end = FirstSatisfaction(0, index_.size(), s);
  return make_pair(match_begin, match_end - match_begin);
}

// Getting called during search, not during indexing. 
// lexicographically compare two strings represented by pointer and length
// comparisons return positive/negative/zero, a la strcmp
// If second_wins is true, 
//     compare s1 to s2+$, where $ represents an infinitely large value
int64 SuffixIndex::Compare(uint64 corpus_position, uint64 l1, 
			   uint32 *v2, uint64 l2, bool second_wins) {
  // if (v1 == v2) return 0;
  uint64 shorter = min(l1, l2);
  for (uint64 c=0; c<shorter; c++) {
    uint32 t1 = (*corpus_)[corpus_position + c];
    uint32 t2 = v2[c];
    /* cout << "Compare "
       << " corpus_position = " << corpus_position
       << " l1 = " << l1
       << " l2 = " << l2
       << " c = " << c
       << " t1 = " << t1
       << " t2 = " << t2
       << endl; */
    if (t1 < t2) return -1;
    if (t2 < t1) return 1;
  }
  if (second_wins && (shorter == l2)) return -1;
  return l1 - l2;
}

/*
// Verify that the index is an index
void SuffixIndex::VerifySort() {
  cout << "SuffixIndex::VerifySort\n";
  cout << "index_.size():" << index_.size() << endl;
  uint64 size = corpus_->size();
  cout << "corpus_->size():" << corpus_->size() << endl;
  for (uint64 i=0; i+1 < index_.size(); i++) {
    uint64 p0 = index_[i];
    uint32 * c0 = data_ + p0;
    uint64 p1 = index_[i+1];
    uint32 * c1 = data_ + p1;
    CHECK(Compare(c0, size - p0, c1, size - p1, false) < 0);
    CHECK(Compare(c1, size - p1, c0, size - p0, false) > 0);
  }
  cout << "::Verified\n";
}
*/
